package top.ivansong92.example.leetcode.learning.data.struct.linklist;


import java.util.*;

public class TestExample {
    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {}
        ListNode(int x) {
            val = x;
        }

        public static ListNode attrToListNode(int[] attr) {
           if (attr == null || attr.length == 0) {
               return null;
           }
           ListNode head = new ListNode(attr[0]);
           ListNode cur = head;
           for(int i = 1; i < attr.length; i ++) {
               cur.next = new ListNode(attr[i]);
               cur = cur.next;
           }
           return head;
        }

        @Override
        public String toString() {
            StringBuffer stringBu = new StringBuffer();
            stringBu.append("[");
            ListNode cur = this;
            while (cur != null) {
                stringBu.append(cur.val + "->");
                cur = cur.next;
            }
            stringBu.append("null]");
            return stringBu.toString();
        }
    }

    /**
     * 删除倒数第n个节点
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/42/
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode index = head;
        int size = 0;
        while (index != null) {
            size++;
            index = index.next;
        }
        int k = size - n;
        if (k == 0 && size == 1) {
            return null;
        }
        if (k == 0 && size > 1) {
            head = head.next;
            return head;
        }
        index = head;
        while (index != null) {
            k--;
            if (k == 0) {
                ListNode node = index.next;
                index.next = node.next;
                node.next = null;
                break;
            }
            index = index.next;
        }
        return head;
    }


    public ListNode removeNthFromEnd2(ListNode head, int n) {
        List<ListNode> nodes = new ArrayList<>();
        ListNode index = head;
        while (index != null) {
            nodes.add(index);
            index = index.next;

        }
        int k = nodes.size() - n;
        if (k == 0 && nodes.size() == 1) {
            return null;
        }
        if (k == 0 && nodes.size() > 1) {
            head = head.next;
            return head;
        }
        if (k == nodes.size()) {
            return null;
        }
        ListNode node = nodes.get(k);
        if (k == nodes.size() - 1) {
            nodes.get(k-1).next = null;
            node = null;
            return head;
        }
        node.val = node.next.val;
        node.next = node.next.next;
        return head;
    }

    public ListNode removeNthFromEndV3(ListNode head, int n) {
        if (head == null || n <= 0 || (head.next == null && n == 1)) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node1 = dummy, node2 = dummy;
        for(int i = 0; i < n + 1; i ++) {
            if (node1 == null) {
                return null;
            }
            node1 = node1.next;
        }

        while (node1 != null) {
            node1 = node1.next;
            node2 = node2.next;
        }

        node1 = node2.next;
        node2.next = node1.next;
        node1.next = null;
        return dummy.next;
    }


    /**
     * 206. 反转链表
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/43/
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode res = new ListNode(head.val);

        ListNode cur = head.next;
        while(cur != null) {
            ListNode node = new ListNode(cur.val);
            node.next = res;
            res = node;
            cur = cur.next;

        }
        return res;
    }

    public ListNode reverseListV2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode pre = null, cur = head, next;

        while(cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 合并两个有序链表
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/44/
     * @param l1
     * @param l2
     * @return
     */

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode res = new ListNode(0);
        ListNode index = res;
        while (true) {
            if (l1 == null) {
                index.next = l2;
                break;
            }
            if (l2 == null) {
                index.next = l1;
                break;
            }

            if (l1.val > l2.val) {
                index.next = l2;
                l2 = l2.next;
            } else {
                index.next = l1;
                l1 = l1.next;
            }
            index = index.next;
        }
        return res.next;
    }


    /**
     *
     *  234. 回文链表
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/45/
     * https://leetcode-cn.com/problems/palindrome-linked-list/
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        List<ListNode> listNodes = new ArrayList<>();
        while (head != null) {
            listNodes.add(head);
            head = head.next;
        }

        if (listNodes.size() <= 1) {
            return true;
        }

        int index = listNodes.size() / 2;
        ListNode node = listNodes.get(index);
        if (listNodes.size() % 2 != 0) {
            node = node.next;
        }

        while (node != null) {
            ListNode com = listNodes.get(--index);
            if (com.val != node.val) {
                return false;
            }
            node = node.next;
        }
        return true;
    }

    public boolean isPalindromeV2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        if (head.next.next == null) {
            return head.val == head.next.val;
        }

        //1、计算长度
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            len ++;
        }
        //2、找到长度一半的位置，根据位置分割链表：偶数会分割成两个一样的，奇数前一个会比后面一个多一个节点，不过比较的时候直接忽略就行
        int step = (len / 2 + len % 2) - 1;
        cur = head;
        for(int i = 0; i < step; i ++) {
            cur = cur.next;
        }

        ListNode cur1 = head, cur2 = cur.next;
        cur.next = null;
        //3、翻转后面的链表
        cur2 = reverseListV2(cur2);
        //4、比较两个链表值是否相等
        while (cur1 != null && cur2 != null) {
            if (cur1.val != cur2.val) {
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }

    public boolean isPalindrome1(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        int size = 0;
        ListNode index = head;
        while (index != null) {
            size ++;
            index = index.next;
        }

        ListNode left = head;
        ListNode right = head.next;
        int half = size / 2;
        if (size % 2 == 0) {
            half --;
        }
        while (half > 0) {
            ListNode next = right.next;
            right.next = left;
            left = right;
            right = next;
            half --;
        }

        if (size % 2 == 1) {
           left = left.next;
        }
        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }

        return true;
    }


    /**
     * 链表是否有环
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/46/
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode fr = head;
        ListNode se = head;
        while(fr != null || se != null) {
            fr = fr.next;
            se = se != null && se.next != null ? se.next.next : null;
            if (fr != null && se != null && fr == se) {
                return true;
            }
        }
        return false;
    }

    /**
     * 203. 移除链表元素
     * https://leetcode-cn.com/problems/remove-linked-list-elements/
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(val != 0 ? 0 : -1);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while (cur != null) {
            if (cur.next != null && cur.next.val == val) {
                ListNode next = cur.next;
                cur.next = next.next;
                next.next = null;
            } else {
                cur = cur.next;
            }

        }
        return dummyHead.next;
    }

    public ListNode removeElements2(ListNode head, int val) {
       if (head == null) {
           return null;
       }
       head.next = removeElements2(head.next, val);
       if (head.val == val) {
           return head.next;
       } else {
           return head;
       }
    }


    /**
     * 160. 相交链表
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Set<ListNode> filter = new HashSet<>();
        ListNode indexA = headA, indexB = headB;
        while (indexA != null || indexB != null) {
            if (indexA != null) {
                if (filter.contains(indexA)) {
                    return indexA;
                }
                filter.add(indexA);
                indexA = indexA.next;
            }

            if (indexB != null) {
                if (filter.contains(indexB)) {
                    return indexB;
                }
                filter.add(indexB);
                indexB = indexB.next;
            }
        }
        return null;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode index1 = headA, index2 = headB;
        while (index1 != index2) {
            index1 = (index1 != null ? index1.next : headB);
            index2 = (index2 != null ? index2.next : headA);
        }
        return index1;
    }


    /**
     * 148. 排序链表
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        List<ListNode> list = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        list.sort(Comparator.comparing(e-> e.val));
        ListNode res = new ListNode();
        node = res;
        for(ListNode no : list) {
            node.next = new ListNode(no.val);
            node = node.next;
        }
        return res.next;
    }


    /**
     * 剑指 Offer 18. 删除链表的节点
     * @param head
     * @param val
     * @return
     */
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        ListNode index = head;
        while (index != null) {
            if (index.next != null && index.next.val == val) {
                index.next = index.next.next;
                break;
            }
            index = index.next;
        }
        return head;
    }
}
